//--------------------------------------------------------------------
//
//  Laboratory 4                                         OrderedList.h
//
//  Class declaration for the array implementation of the Ordered
//  List ADT -- inherits the array implementation of the List ADT
//  (Laboratory 3)
//
//--------------------------------------------------------------------

#ifndef ORDEREDLIST_H
#define ORDEREDLIST_H

#include <stdexcept>
#include <iostream>

using namespace std;

#include "ListArray.h"

template < typename DataType, typename KeyType >
class OrderedList : public List<DataType>
{
public:
   // Constructor
   OrderedList ( int maxNumber = List::DEFAULT_MAX_LIST_SIZE )
      :List(maxNumber)
   {

   }

   // Modified (or new) list manipulation operations
   virtual void insert ( const DataType &newDataItem ) throw ( logic_error )
   {
      if (isFull()) 
      {
         throw logic_error("list is full");
      }
      KeyType key = newDataItem.getKey();
      int index;
      if(binarySearch(key, index))
      {
         moveToNth(index);
         List<DataType>::replace(newDataItem);
      }
      else
      {

         moveToNth(max(0,index));
         List<DataType>::insert(newDataItem);
      }
   }

   virtual void replace ( const DataType &newDataItem ) throw ( logic_error )
   {
      if (isEmpty()) 
      {
         throw logic_error("list is empty");
      }
      List<DataType>::remove();
      insert(newDataItem);
   }

   bool retrieve ( const KeyType& searchKey, DataType &searchDataItem )
   {
      int indexFound;
      bool foundItem = binarySearch(searchKey, indexFound);
      if(foundItem)
      {
         moveToNth(indexFound);
         searchDataItem = getCursor();
         return true;
      }
      return false;
   }

   // Output the list structure -- used in testing/debugging
   void showStructure () const
   {
      if ( size == 0 )
         cout << "Empty list" << endl;
      else
      {
         cout << "size = " << size
            <<  "   cursor = " << cursor << endl;
         for ( int j = 0 ; j < maxSize ; ++j )
            cout << j << "\t";
         cout << endl;
         for ( int j = 0 ; j < size ; ++j ) {
            if( j == cursor ) {
               cout << "[" << dataItems[j].getKey() << "]\t";
            } else {
               cout << dataItems[j].getKey() << "\t";
            }
         }
         cout << endl;
      }
   }


   // In-lab operations
   void merge ( const OrderedList<DataType,KeyType> &other ) throw ( logic_error )
   {
   }

   bool isSubset ( const OrderedList<DataType,KeyType> &other )
   {
      return false;
   }

private:

   // Binary search routine. Searches a list for the data item with
   // key searchKey. If the data item is found, then returns true with
   // index returning the array index of the entry containing searchKey.
   // Otherwise, returns false with index returning the array index of the
   // entry containing the largest key that is smaller than searchKey
   // (or -1 if there is no such key).
   bool binarySearch ( KeyType searchKey, int &index )
   {
      int low  = 0,           // Low index of current search range
         high = size - 1;    // High index of current search range
      bool result;            // Result returned

      while ( low <= high )
      {
         index = ( low + high ) / 2;               // Compute midpoint
         if ( searchKey < dataItems[index].getKey() )
            high = index - 1;                      // Search lower half
         else if ( searchKey > dataItems[index].getKey() )
            low = index + 1;                       // Search upper half
         else
            break;                                 // searchKey found
      }

      if ( low <= high )
         result = true;       // searchKey found
      else
      {
         index = high;        // searchKey not found, adjust index
         result = false;
      }
      return result;
   }
public:
   // Inheritance using templates is somewhat ugly in C++. It feels like you
   // should be able to access base class member functions and data without the
   // scope resolution operator. Sadly, you cannot when using templates.
   // See http://www.parashift.com/c++-faq-lite/templates.html#faq-35.19
   // Tell compiler to use these base class methods.
   using List<DataType>::remove;
   using List<DataType>::clear;
   using List<DataType>::isEmpty;
   using List<DataType>::isFull;
   using List<DataType>::gotoBeginning;
   using List<DataType>::gotoEnd;
   using List<DataType>::gotoNext;
   using List<DataType>::gotoPrior;

   // Tell compiler to use these base class data members
   using List<DataType>::maxSize;
   using List<DataType>::cursor;
   using List<DataType>::size;
   using List<DataType>::dataItems;
};

#endif // #ifndef ORDEREDLIST_H

